{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- https://www.fluentcpp.com/getthemap/\n",
    "- https://www.youtube.com/watch?v=bXkWuUe9V2I\n",
    "- https://www.youtube.com/watch?v=2olsGf6JIkU\n",
    "- https://www.bilibili.com/video/BV1WH4y1X7Mr\n",
    "- https://www.bilibili.com/video/BV1Ub411H7A3\n",
    "- https://www.fluentcpp.com/2018/07/10/105-stl-algorithms-in-less-than-an-hour/\n",
    "- https://zhuanlan.zhihu.com/p/79088038\n",
    "- https://github.com/mo-xiaoming/stl-algorithms\n",
    "- https://github.com/CppCon/CppCon2018/issues/8\n",
    "- https://zhuanlan.zhihu.com/p/657922639\n",
    "- https://blog.csdn.net/flushhip/article/details/82858933\n",
    "- https://en.cppreference.com/w/cpp/header/algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "把标准算法当作语言工具，优先表达意图，再关注实现细节。\n",
    "\n",
    "Expressive Code：明示“做什么”的代码风格，利用 STL 算法的抽象与标准词汇实现意图表达。\n",
    "- 手写循环的两大风险是越界访问和空集合处理不当，都会导致 Undefined Behavior；标准算法通过边界检查与约定接口规避这些问题。\n",
    "- 学习策略：按照功能区域构建“世界地图”，熟悉可组合的“符文”，把算法当作团队共享的沟通语言。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 核心理念与可组合符文\n",
    "\n",
    "理解算法与容器的解耦、迭代器模型，是后续掌握全部算法的基础。\n",
    "\n",
    "- **算法 + 容器的分离**：算法通过迭代器操作范围，不绑定具体容器。\n",
    "- **迭代器类别**：输入、输出、前向、双向、随机访问等，决定可用算法。\n",
    "- **命名模式解析**：\n",
    "  - `*_if` 表达条件筛选。\n",
    "  - `*_copy` 表示复制结果到新范围。\n",
    "  - `is_*` 返回布尔值。\n",
    "  - `adjacent_*`、`heap_*` 等具有特定语义。\n",
    "- **范围 vs. 元素**：掌握范围标记（`[begin, end)`）及半开区间惯例。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 秘密符文 (Secret Runes)\n",
    "\n",
    "符文可以与其他算法结合，以生成新的算法或增强其功能。\n",
    "\n",
    "1. **stable**：确保算法在执行时保持元素的相对顺序（例如：`stable_partition`, `stable_sort`）。\n",
    "2. **is**：检查集合是否满足某种属性，返回布尔值（例如：`is_sorted`, `is_partitioned`, `is_heap`）。\n",
    "3. **is_until**：返回第一个不满足谓词的位置的迭代器（例如：`is_sorted_until`）。\n",
    "4. **copy**：结合在原地操作的算法，使其在新集合中产生输出，而输入集合保持不变（例如：`remove_copy`）。\n",
    "5. **if**：允许算法接受一个谓词，而不是一个具体的值（例如：`find_if`）。\n",
    "6. **_n**：改变算法的接口，使其接受起始迭代器和大小（size），而不是起始迭代器和结束迭代器（例如：`fill_n`）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 在 Jonathan Boccara 的演讲中，“Runes” 是一种形象化比喻：他把算法命名中的前缀、后缀（如 `stable_`, `_copy`, `_if`, `_n` 等）视作可以叠加在基础算法上的“魔法符记”"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 查询属性 (Querying a Property), 单个范围：\n",
    "\n",
    "1. `all_of`：判断所有元素是否都满足谓词。\n",
    "\n",
    "  ◦ *注：对空集合返回* *True**。*\n",
    "\n",
    "2. `any_of`：判断至少一个元素是否满足谓词。\n",
    "\n",
    "  ◦ *注：对空集合返回* *False**。*\n",
    "\n",
    "3. `none_of`：判断没有元素满足谓词。\n",
    "\n",
    "  ◦ *注：对空集合返回* *True**。*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 查询类算法（Queries / 非修改操作）\n",
    "\n",
    "按“遍历/计数”“匹配”“性质检测”三大块记忆，可迅速定位需要的算法。\n",
    "\n",
    "遍历与计数\n",
    "\n",
    "- `for_each`：对区间内每个元素执行给定函数，通常用于副作用；不能替代所有循环。\n",
    "- `for_each_n`：从起始迭代器开始，对连续 `n` 个元素执行函数。\n",
    "- `count` / `count_if`：统计等于指定值或满足谓词的元素个数。\n",
    "- `std::invoke`：统一调用函数指针、成员函数指针和函数对象。\n",
    "\n",
    "查找单值（无序范围）\n",
    "\n",
    "- `find`：查找首个等于目标值的元素迭代器。\n",
    "- `find_if` / `find_if_not`：查找首个满足/不满足谓词的元素。\n",
    "\n",
    "查找子序列与匹配\n",
    "\n",
    "- `find_end`：查找子序列最后一次出现的位置。\n",
    "- `find_first_of`：查找第一个属于另一范围任一元素的位置。\n",
    "- `adjacent_find`：查找首个相邻且相等（或满足二元谓词）的元素对。\n",
    "- `search`：查找子序列第一次完整出现的位置。\n",
    "- `search_n`：查找连续 `n` 个等于给定值的元素区间。\n",
    "\n",
    "区间比较\n",
    "\n",
    "- `mismatch`：返回两个范围首个不相等元素的迭代器对。\n",
    "- `equal`：判断两个范围是否逐元素相等。\n",
    "- `lexicographical_compare`：按字典序比较两个范围。\n",
    "\n",
    "整体性质判定\n",
    "\n",
    "- `all_of` / `any_of` / `none_of`：判断是否全部/至少一个/完全没有元素满足谓词。\n",
    "- `is_partitioned`：判断区间是否已按谓词划分。\n",
    "- `is_sorted` / `is_sorted_until`：检测区间整体或前缀是否单调非降。\n",
    "- `is_heap` / `is_heap_until`：检测区间整体或前缀是否满足最大堆性质。\n",
    "- `is_permutation`：判断两个范围是否包含相同多重集元素。\n",
    "\n",
    "二分查找与区间定位（要求已排序范围）\n",
    "\n",
    "- `binary_search`：判断某值是否存在，返回布尔值。\n",
    "- `lower_bound`：返回第一个不小于目标值的位置。\n",
    "- `upper_bound`：返回第一个大于目标值的位置。\n",
    "- `equal_range`：同时给出 `[lower_bound, upper_bound)` 的上下界迭代器对。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 非结构性修改（Modifying Sequence Operations）\n",
    "\n",
    "这些算法不改变容器结构，仅修改或搬运值，需要注意输出区间合法性。\n",
    "\n",
    "拷贝家族\n",
    "- `copy` / `copy_if` / `copy_n`：顺序复制元素到目标范围，`copy_if` 仅复制满足谓词的元素。\n",
    "- `copy_backward`：从尾到头复制，安全处理重叠区间。\n",
    "\n",
    "移动家族\n",
    "- `move` / `move_backward`：与拷贝类似，但对元素执行 `std::move`，转移资源所有权。\n",
    "\n",
    "交换家族\n",
    "- `swap`：交换两个对象的值。\n",
    "- `swap_ranges`：交换两个范围的对应元素。\n",
    "- `iter_swap`：交换两个迭代器指向的元素。\n",
    "\n",
    "变换\n",
    "- `transform`：对每个元素（一元或二元）应用函数并写入输出迭代器。\n",
    "\n",
    "替换家族\n",
    "- `replace` / `replace_if`：就地替换等于目标值或满足谓词的元素。\n",
    "- `replace_copy` / `replace_copy_if`：复制时进行替换。\n",
    "\n",
    "填充家族\n",
    "- `fill` / `fill_n`：将范围或前 `n` 个元素赋同一值。\n",
    "\n",
    "生成家族\n",
    "- `generate` / `generate_n`：调用无参函数为范围或前 `n` 个位置生成新值。\n",
    "\n",
    "删除家族（逻辑删除）\n",
    "- `remove` / `remove_if`：保留元素前移，返回逻辑末尾迭代器。\n",
    "- `remove_copy` / `remove_copy_if`：复制时排除目标值或满足谓词的元素。\n",
    "\n",
    "去重家族\n",
    "- `unique`：移除相邻重复值，返回新逻辑末尾。\n",
    "- `unique_copy`：输出去重后的序列。\n",
    "\n",
    "逆序与旋转\n",
    "- `reverse` / `reverse_copy`：就地逆序或将逆序结果写入新范围。\n",
    "- `rotate` / `rotate_copy`：循环平移元素，使中点成为新首元素。\n",
    "\n",
    "移位操作（C++20）\n",
    "- `shift_left` / `shift_right`：在同一范围内整体左移或右移元素。\n",
    "\n",
    "随机化\n",
    "- `shuffle`：使用随机数生成器打乱元素顺序。\n",
    "- `sample`：从输入范围随机抽取指定数量样本。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 排列与顺序选择（Permutation Operations）\n",
    "\n",
    "按字典序生成排列或定位特定位置的元素。\n",
    "\n",
    "- `next_permutation`：生成字典序下一个排列，若已最大则变为最小并返回 `false`。\n",
    "- `prev_permutation`：生成字典序上一个排列，若已最小则变为最大并返回 `false`。\n",
    "- `nth_element`：将第 `n` 个位置调整到完全排序后的正确位置，左侧元素不大于它，右侧不小于它。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 分区、排序与堆（Structure Changers）\n",
    "\n",
    "关注“分区”“全排序/部分排序”“堆结构”三个维度，明确是否保持稳定性。\n",
    "\n",
    "分区（Partitioning Operations）\n",
    "- `partition`：按谓词将元素划分为前后两部分。\n",
    "- `stable_partition`：分区同时保持相对顺序。\n",
    "- `partition_copy`：将真值区和假值区分别复制到两个输出范围。\n",
    "- `partition_point`：在已分区范围中返回真值区与假值区的边界。\n",
    "\n",
    "排序（Sorting Operations）\n",
    "- `sort`：默认按非降序排序，可自定义比较器。\n",
    "- `stable_sort`：稳定排序，保持相等元素次序。\n",
    "- `partial_sort` / `partial_sort_copy`：仅保证前 `k` 个元素有序。\n",
    "- `inplace_merge`：在同一容器内合并两个相邻的有序子区间。\n",
    "\n",
    "堆算法（Heap Operations）\n",
    "- `make_heap`：将范围元素重排成最大堆。\n",
    "- `push_heap`：将新元素插入堆尾后恢复堆序。\n",
    "- `pop_heap`：将堆顶元素移动到尾部，并保持剩余部分为堆。\n",
    "- `sort_heap`：在堆的基础上生成完全排序序列。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 合并与包含（Merge Operations）\n",
    "\n",
    "处理两个已排序序列的合成与包含关系。\n",
    "\n",
    "- `merge`：将两个有序范围合并为一个有序序列。\n",
    "- `inplace_merge`：在原地合并两个相邻有序子区间（与 分区、排序与堆 提示呼应）。\n",
    "- `includes`：判断第一个有序范围是否完全包含第二个范围。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 集合算法（Set Operations on Sorted Ranges）\n",
    "\n",
    "输入需有序，复杂度线性。*\n",
    "\n",
    "- `set_union`：生成并集。\n",
    "- `set_intersection`：生成交集。\n",
    "- `set_difference`：生成差集（存在于第一个集合但不在第二个集合中）。\n",
    "- `set_symmetric_difference`：生成对称差集（恰属于一个集合的元素）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最值算法（Min/Max Operations）\n",
    "\n",
    "用于比较单值或查找范围内最值，常与比较器搭配。\n",
    "\n",
    "- `min` / `max`：返回两个值中较小/较大者。\n",
    "- `minmax`：同时返回最小值和最大值（`std::pair` 或结构化绑定）。\n",
    "- `clamp`：将值限制在指定区间内。\n",
    "- `min_element` / `max_element`：返回范围内最小/最大的元素迭代器。\n",
    "- `minmax_element`：一次遍历同时找出最小与最大元素迭代器。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 数值算法（Numeric Operations）\n",
    "\n",
    "多用于前缀和、扫描、内积等数值处理，可结合并行执行策略。\n",
    "\n",
    "- `iota`：从起始值开始依次递增填充范围。\n",
    "- `accumulate`：按顺序累加元素，可自定义二元运算。\n",
    "- `reduce`：C++17 引入的归约接口，可并行。\n",
    "- `inner_product`：计算两个等长范围的内积。\n",
    "- `partial_sum`：生成所有前缀和序列。\n",
    "- `exclusive_scan` / `inclusive_scan`：生成排除当前元素或包含当前元素的前缀扫描结果。\n",
    "- `transform_reduce`：先对元素应用变换，再进行归约。\n",
    "- `transform_exclusive_scan` / `transform_inclusive_scan`：变换与扫描结合。\n",
    "- `adjacent_difference`：计算相邻元素差值序列。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 原始内存管理与销毁\n",
    "\n",
    "与智能指针、自定义内存池配合时，需要显式构造/销毁对象。\n",
    "\n",
    "- `uninitialized_default_construct` / `_n`：在未初始化内存中默认构造对象。\n",
    "- `uninitialized_value_construct` / `_n`：在未初始化内存中值初始化对象。\n",
    "- `uninitialized_fill` / `_n`：在未初始化内存中构造多个相同值对象。\n",
    "- `uninitialized_copy` / `_n`：复制元素到未初始化内存并构造。\n",
    "- `uninitialized_move` / `_n`：移动元素到未初始化内存并构造。\n",
    "- `destroy` / `destroy_at` / `destroy_n`：显式调用析构函数，与 `uninitialized_*` 系列配套使用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 搜索器扩展（Searchers / Secret Runes）\n",
    "\n",
    "优化字符串或任意可比较序列的子串搜索\n",
    "\n",
    "- `default_searcher`：基于 `search` 的默认策略。\n",
    "- `boyer_moore_searcher`：使用 Boyer–Moore 算法加速匹配。\n",
    "- `boyer_moore_horspool_searcher`：Boyer–Moore Horspool 变体，构建跳表开销更低。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 算法组合与常见开发模式\n",
    "\n",
    "*注释：组合算法时需关注迭代器类别、输出位置及容器操作配合。*\n",
    "\n",
    "- 惯用组合示例：\n",
    "  - `partition` + `copy`：先划分后复制满足条件的元素。\n",
    "  - `transform` + `accumulate`：映射后再归约，实现简洁的函数式风格。\n",
    "- 插入迭代器：`back_inserter`、`front_inserter`、`inserter`，允许将输出直接写回容器。\n",
    "- 常见惯用法：`remove/erase`、`unique/erase`、`stable_partition` 等模式通过封装或工具函数降低样板代码。\n",
    "- 倡导使用标准算法作为团队共享词汇，提高表达力、安全性与可维护性。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
